package com.zhang.InsertSort;

import com.zhang.common.Constants;

import java.util.Arrays;

/**
 * https://www.runoob.com/w3cnote/insertion-sort.html
 *
 * @author Ryan.Li
 * @date 2022/1/24
 **/
public class TestInsertSort {
    public static void main(String[] args) throws Exception {
        int[] sort = insertSort(Constants.ARR);
        for (int value : sort) {
            System.out.println("value = " + value);
        }
    }

    /**
     * 插入排序
     *
     * @param sourceArray
     * @return
     */
    public static int[] insertSort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}
